The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(*(x1)) → *(1(x1))
1(*(x1)) → 0(#(x1))
#(0(x1)) → 0(#(x1))
#(1(x1)) → 1(#(x1))
#($(x1)) → *($(x1))
#(#(x1)) → #(x1)
#(*(x1)) → *(x1)

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2.
The certificate found is represented by the following graph.

Start state: 1877
Accept states: [1878, 1879, 1880]
Transitions:
1877→1878[0_1|0]
1877→1879[1_1|0]
1877→1880[#_1|0, *_1|1]
1877→1877[*_1|0, $_1|0]
1877→1881[1_1|1]
1877→1882[#_1|1, *_1|1]
1877→1883[$_1|1]
1877→1884[1_1|2]
1881→1878[*_1|1]
1882→1879[0_1|1]
1882→1881[0_1|1]
1882→1884[0_1|1]
1883→1880[*_1|1]
1883→1882[*_1|1]
1883→1884[1_1|2]
1884→1879[*_1|2]
1884→1881[*_1|2]
1884→1884[*_1|2]

(2) BOUNDS(O(1), O(n^1))